/*
https://leetcode.cn/problems/delete-and-earn/description/?envType=problem-list-v2&envId=AnEpLQwV
740. 删除并获得点数
*/

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        vector<int>dp(10003,0);
        int maxx=ranges::max(nums);
        for(int i=0;i<nums.size();i++)
        {
            dp[nums[i]]+=nums[i];
        }
        int sum=0;
        for(int i=2;i<=maxx+1;++i){
            if(dp[i]==0){
                sum+=max(dp[i-1],dp[i-2]);
                dp[i-1]=0;
            }else
            dp[i]=max(dp[i-1],dp[i-2]+dp[i]);
        }
        return sum;
    }
};
